package org.example.day;

import java.util.Arrays;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/06/28 10:39
 */
//给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time ，分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠：
//
//
// 一位需要 付费 的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，开销为 cost[i] 单位的钱。
// 一位 免费 的油漆匠，刷 任意 一堵墙的时间为 1 单位，开销为 0 。但是必须在付费油漆匠 工作 时，免费油漆匠才会工作。
//
//
// 请你返回刷完 n 堵墙最少开销为多少。
//
//
//
// 示例 1：
//
// 输入：cost = [1,2,3,2], time = [1,2,3,2]
//输出：3
//解释：下标为 0 和 1 的墙由付费油漆匠来刷，需要 3 单位时间。同时，免费油漆匠刷下标为 2 和 3 的墙，需要 2 单位时间，开销为 0 。总开销为
//1 + 2 = 3 。
//
//
// 示例 2：
//
// 输入：cost = [2,3,4,2], time = [1,1,1,1]
//输出：4
//解释：下标为 0 和 3 的墙由付费油漆匠来刷，需要 2 单位时间。同时，免费油漆匠刷下标为 1 和 2 的墙，需要 2 单位时间，开销为 0 。总开销为
//2 + 2 = 4 。
//
//
//
//
// 提示：
//
//
// 1 <= cost.length <= 500
// cost.length == time.length
// 1 <= cost[i] <= 10⁶
// 1 <= time[i] <= 500
//
//
// Related Topics 数组 动态规划 👍 60 👎 0

public class Solution2742 {

    public static void main(String[] args) {
        Solution2742 solution2742 = new Solution2742();
        System.out.println(solution2742.paintWalls(new int[]{8,7,5,15}, new int[]{1,1,2,1}));
    }

    public int paintWalls(int[] cost, int[] time) {
        //免费油漆工刷的快， 尽量让付费油漆工刷 便宜+时间开销大的墙
        //按照  成本 小时的单价 降序， 付费油漆工 优先做 单价低 + 成本高
        int[][] costAvg = new int[cost.length][3];
        for (int i = 0; i < cost.length; i++) {
            costAvg[i][0] = cost[i] * 500 / time[i];
            costAvg[i][1] = cost[i];
            costAvg[i][2] = time[i];
        }
        Arrays.sort(costAvg, (p,q) -> {
            if(p[0] > q[0]){
                return 1;
            }else if(p[0] == q[0]){
                return p[1] - q[1];
            }
            return -1;
        });

        int costSum = 0;
        int timeSum = 0;

        for (int i = 0; i < costAvg.length; i++) {
            costSum += costAvg[i][1];
            timeSum += costAvg[i][2];
            if(timeSum + i + 1 >= time.length){
                break;
            }
        }

        return costSum;
    }
    /**
     * @Description:
     *
     * @auther: wyatt
     * @date: 10:47 2024/6/28
    */
    @Deprecated
    public int paintWalls2(int[] cost, int[] time) {
        //免费油漆匠免费，刷任意墙只需要时间1 ，但是免费油漆匠的刷墙数 不能超过付费
        //只需要找出付费油漆工刷 一半墙的最少花费
        int num = (cost.length / 2) + (cost.length % 2 == 0 ? 0 : 1);

        return 0;
    }

}
